#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

//typedef long long LL;
//const int N = 1e5 + 10;
//LL a[N];
//
//LL n;
//
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i];
//	}
//
//	sort(a + 1, a + 1 + n);
//
//	LL ret = 0;
//	for (int i = 1; i <= n / 2; i++)
//	{
//		ret += (a[n + 1 - i] - a[i]);
//	}
//
//	cout << ret;
//
//	return 0;
//}

//typedef long long LL;
//const int N = 2e5 + 10;
//
//LL a[N], n;
//
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i];
//	}
//
//	LL sum = 0, ret = -1e6;
//	for (int i = 1; i <= n; i++)
//	{
//		
//			sum += a[i];
//			ret = max(ret, sum);
//		if(sum < 0)
//			sum = 0;
//	}
//
//	cout << ret << endl;
//
//	return 0;
//}

//typedef long long LL;
//const int N = 1e5 + 10;
//
//LL a[N], w, n;
//
//int main()
//{
//	cin >> w >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i];
//	}
//
//	sort(a + 1, a + 1 + n);
//	int left = 1, right = n;
//	int count = 0;
//	while (left <= right)
//	{
//		if (a[left] + a[right] > w)
//			right--;
//		else left++, right--;
//
//		count++;
//	}
//
//	cout << count;
//
//	return 0;
//}

//int m, n, k, l, d;
//
//const int N = 1010;
//
//struct node
//{
//	int index;
//	int cnt;
//}row[N],col[N];
//
//bool cmp1(const node& x, const node& y)
//{
//	return x.cnt > y.cnt;
//}
//
//bool cmp2(const node& x, const node& y)
//{
//	return x.index < y.index;
//}
//
//int main()
//{
//	cin >> m >> n >> k >> l >> d;
//	for (int i = 1; i <= m; i++) row[i].index = i;
//	for (int i = 1; i <= n; i++) col[i].index = i;
//	while (d--)
//	{
//		int x, y, p, q; cin >> x >> y >> p >> q;
//		if (x == p)
//		{
//			col[min(y, q)].cnt++;
//		}
//		else if (y == q)
//		{
//			row[min(x, p)].cnt++;
//		}
//	}
//
//	sort(row + 1, row + 1 + m, cmp1);
//	sort(col + 1, col + 1 + n, cmp1);
//
//	sort(row + 1, row +1 + k, cmp2);
//	sort(col + 1, col + 1 + l, cmp2);
//
//	for (int i = 1; i <= k; i++)
//	{
//		cout << row[i].index << " ";
//	}
//	cout << endl;
//	for (int i = 1; i <= l; i++)
//	{
//		cout << col[i].index << " ";
//	}
//
//	return 0;
//}



//typedef long long LL;
//const int N = 25;
//int n, m, k, V = INT_MIN;
//
//vector<vector<LL>> a(N, vector<LL>(N)); 
//int row[N];
//
//int main()
//{
//	cin >> n >> m >> k;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			cin >> a[i][j];
//		}
//	}
//
//	vector<vector<LL>> tmp = a;
//
//
//	for (int k = 0; k < (1 << n); k++)
//	{
//		int val = k;
//		int count = n;
//		int i = 1;
//		while (count--)
//		{
//			int m = val % 2;
//			row[i] = m;
//			val /= 2;
//			i++;
//		}
//
//		int flag = 0;
//		for (int i = 1; i <= n; i++)
//		{
//			if (row[i] == 1)
//			{
//				flag++;
//			}
//		}
//		if (flag >= k)
//		{
//			memset(row, 0, sizeof(row));
//			continue;
//		}
//
//		int sum = 0;
//
//		for (int x = 1; x <= n; x++)
//		{
//			if (row[x] == 1)
//			{
//				for (int j = 1; j <= m; j++)
//				{
//					sum += tmp[x][j];
//					tmp[x][j] = 0;
//				}
//			}
//		}
//
//		int last = min(k - flag,m);
//		while (last--)
//		{
//			int ret = INT_MIN;
//			int colsum = 0, index = -1;
//			for (int j = 1; j <= m; j++)
//			{
//				for (int i = 1; i <= n; i++)
//				{
//					colsum += tmp[i][j];
//				}
//				if (colsum > ret)
//				{
//					swap(ret, colsum);
//					index = j;
//				}
//
//			}
//
//			sum += ret;
//			for (int i = 1; i <= n; i++)
//			{
//				tmp[i][index] = 0;
//			}
//		}
//
//		
//		V = max(V, sum);
//
//		tmp = a;
//		memset(row, 0, sizeof(row));
//
//
//	}
//
//	cout << V << endl;
//
//	return 0;
//}


